import java.util.Scanner;

/**
 * <p>
 * 堆排序
 * </p>
 * <p>
 * 虽然不论是Java还是C++现在都提供了封装好的优先队列，但学习如何手写堆仍是必不可少的，为了好好学习数据结构（没办法，面试需要手撕堆（bushi））
 * </p>
 * <p>
 * 相信今天的学习之后，你就能更好地理解Java中的PriorityQueue或者C++中的priority_queue了
 * </p>
 * <p>时间复杂度：建立一个堆的时间复杂度是o(n)，插入的时间复杂度是o(log(n))，堆排序的时间复杂度是o(nlog(n))</p>
 *
 * @author 没天赋
 * @since 2025-6-14
 */
public class heapSort {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 输入排序前的数组
        int n = sc.nextInt();
        int[] a = new int[n + 10];
        // 记录一下长度，后面有用
        int len = n;
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
        }
        // 开始创建堆，我们这里以小根堆为例
        // 从 n/2 开始，也就是最后一个有子节点的节点
        for (int i = n / 2; i >= 1; i--) {
            DownAdjust(a, n, i);
        }

        for (int i = 1; i <= n; i++) {
            System.out.print(a[i]+" ");
        }
        System.out.println();

        // 插入元素
        a[++n] = sc.nextInt();
        len++;
        UpAdjust(a, n, n);

        // 弹出堆顶值
        for (int i = 0; i < n; i++) {
            // 顺序打印，这就是排好序的了，因为每次弹出的都是最小的
            System.out.print(a[1] + " ");
            // 每次让最后一个叶子结点到堆顶，再向下调整
            a[1] = a[len--];
            DownAdjust(a, len, 1);
        }
        System.out.println();
    }

    /**
     * 向下调整（创建堆，弹出堆顶元素）
     *
     * @param a
     * @param n
     * @param i
     */
    public static void DownAdjust(int[] a, int n, int i) {
        // 从当前节点开始，往下调整
        int now = i, next;
        // 还有叶子节点就可以一直往下
        while (now * 2 <= n) {
            // next为左子节点（只要能进入循环证明至少有一个节点，那左孩子肯定存在）
            next = now * 2;
            // 判断右孩子是否存在，存在的话他和左孩子哪个小
            if (next + 1 <= n && a[next + 1] < a[next]) {
                next = next + 1;
            }
            // 如果当前父节点已经是最小，那就不用向下调整了，跳出循环
            if (a[now] <= a[next]) {
                break;
            }
            // 否则交换父节点和最小子节点的值，继续向下调整
            swap(a, now, next);
            now = next;
        }
    }

    /**
     * 向上调整（插入元素）
     * @param a
     * @param n
     * @param i
     */
    public static void UpAdjust(int[] a, int n, int i) {
        // 从当前节点开始，往上调整
        int now = i, next;
        // 还有叶子节点就可以一直往下
        while (now > 1) {
            // next为父节点
            next = now / 2;
            // 如果当前比父节点大，跳出循环
            if (a[now] >= a[next]) {
                break;
            }
            // 否则交换父节点和最小子节点的值，继续向下调整
            swap(a, now, next);
            now = next;
        }
    }

    /**
     * 交换数组中元素
     *
     * @param a
     * @param l
     * @param r
     */
    public static void swap(int[] a, int l, int r) {
        int temp = a[l];
        a[l] = a[r];
        a[r] = temp;
    }
}

/**
 * 测试数据
 * 5
 * 12 5 3 1 78
 * 7
 * -----------
 * 1 5 3 12 78
 * 1 3 5 7 12 78
 */
